﻿#define _CRT_SECURE_NO_WARNINGS

//栈和队列的相互实现
//LeetCode上面的OJ题，无法进行测试

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


//【用队列实现栈】：用两个队列实现栈，并支持栈中的push、top、pop、empty四种操作
//思路：元素在两个队列中来回倒


///////////////////////////////////////////以下：需要用到的队列中的基本操作

//定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//ptail newnode
	if (pq->phead == NULL)
	{//队列为空
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;//newnode
	}
	pq->size++;
}


//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}


// 出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除队头元素、
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}


//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}


//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//这一步在OJ上面需要注释掉，不过why？

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}


///////////////////////////////////////////

//定义新栈的结构
typedef struct
{
	Queue q1;
	Queue q2;
}Mystack;

//创建新栈同时初始化
Mystack* mystackCreate()
{
	Mystack* pst = (Mystack*)malloc(sizeof(Mystack));
	if (pst == NULL)//判断的这一步如果不写，在VS上会报警告，但是OJ题上面不会
	{
		perror("malloc fail");
		exit(-1);
	}
	else {
		QueueInit(&pst->q1);
		QueueInit(&pst->q2);
		return pst;
	}

}

//入新栈
void mystackPush(Mystack* obj, int x)
{
	//往空队列中插入数据
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

//出新栈
int mystackPop(Mystack* obj)
{
	//把已有数据的队列前size-1个元素，导入到空队列中
	//先找出空队列
	Queue* empQ = &obj->q1;//先假设q1是空队列
	Queue* noneQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))//假设错误在调换
	{
		noneQ = &obj->q1;
		empQ = &obj->q2;
	}
	//开始导入
	while (QueueSize(noneQ) > 1)
	{
		int front = QueueFront(noneQ);
		QueuePush(empQ, front);//这里不是取地址，所以得手动出
		QueuePop(noneQ);
	}
	//非空队列只剩下最后一个元素，即是要出栈的元素
	int pop = QueueFront(noneQ);
	QueuePop(noneQ);
	return pop;
}



//取新栈的栈顶元素
int mystackTop(Mystack* obj)
{
	//常规思路就是会认为，同【出新栈】的方法一致，但用出新栈的代码(思路)写取栈顶元素是错误的
	//因为用队列实现栈的操作中，必须要保证至少有一个队列为空，才能进行导数据
	//如果按照出新栈的代码(思路)写取栈顶元素的话，虽然理论上来说是可行的
	//但是因为操作实现后不用出队列，那么最后就会导致出现两个非空队列，再往下进行操作时，将没有空队列可以使用，故实际上这个思路不可行

	////////////////////////////////////
	/*Queue* empQ = &obj->q1;
	Queue* noneQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		noneQ = &obj->q1;
		empQ = &obj->q2;
	}

	while (QueueSize(noneQ) > 1)
	{
		int front = QueueFront(noneQ);
		QueuePush(empQ, front);
		QueuePop(noneQ);
	}

	return QueueFront(noneQ);*/
	////////////////////////////////////

	//取栈顶元素的正确思路：找不为空的队列，取队尾元素(这种思路反而比上面的更简便）
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}



//判空
bool mystackEmpty(Mystack* obj)
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

//销毁新栈
void mystackFree(Mystack* obj)
{
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
	obj = NULL;
}




//【用栈实现队列】：用两个栈实现队列，并支持队列中的push、top、pop、empty四种操作
//思路：元素在两个栈中来回倒


///////////////////////////////////////////以下：需要用到的栈中的基本操作

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int capacity;     //栈的空间大小
	int top;          //栈顶
}ST;

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}


//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}


///////////////////////////////////////////



//定义新队的结构
typedef struct
{
	ST pushST;//新队的定义不用像新栈一样找谁为空，直接就定义谁存数据，谁出数据
	ST popST;
}Myqueue;


//创建新队并初始化
Myqueue* myqueueCreate()
{
	Myqueue* pst = (Myqueue*)malloc(sizeof(Myqueue));
	if (pst == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		STInit(&pst->pushST);
		STInit(&pst->popST);
		return pst;
	}
}

//入新队
void myqueuePush(Myqueue* obj, int x)
{
	StackPush(&obj->pushST, x);
}

//出新队
int myqueuePop(Myqueue* obj)
{
	//看popST是否为空，非空就先pop；为空就先将pushST的数据导入popST，再pop
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))//导数据
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
	//非空
	int top = StackTop(&obj->popST);
	StackPop(&obj->popST);
	return top;
}

//取新队的队头元素
int myqueueTop(Myqueue* obj)
{
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
	return StackTop(&obj->popST);
}

//判空
bool myqueueEmpty(Myqueue* obj)
{
	return StackEmpty(&obj->pushST) && (StackEmpty(&obj->popST));
}

//销毁新队
void myqueueFree(Myqueue* obj)
{
	STDestroy(&obj->pushST);
	STDestroy(&obj->popST);
	free(obj);
	obj = NULL;
}


///无测试



/////////////////////////
////////////////////////
////////////////////////
